package com.desin.modle.sorts;


public class BucketSort {

    /**
     *
     * @param arr 要排序的数组
     * @param bucketSize  每个桶的数据
     */
    public void bucketSort(int[] arr,int bucketSize){
        //求取数组中的最大值和最小值,方便计算要划分多少个桶
        int min = arr[0];
        int max = arr[0];
        for(int j=0;j<arr.length;j++){
            if(arr[j]<min){
                min = arr[j];
            }else if(arr[j]>max){
                max = arr[j];
            }
        }

        //定义两个数组,一个二维数组来定义每个数据所在桶的位置,一个一维数组来定义每个桶的数据量多少，超过平均值就扩容
        int bucketCount = (max - min)/bucketSize + 1;//定义桶的个数
        int[][] bucketArr = new int[bucketCount][bucketSize];
        int[] indexArr = new int[bucketCount];//定义某个桶所拥有的元素个数
        for(int i=0;i<arr.length;i++){
            int bucketIndex = (arr[i] - min)/bucketSize;
            if(indexArr[bucketIndex] == bucketArr[bucketIndex].length){
                //桶扩容
                bucketAddSizeToDouble(bucketArr,bucketIndex);
            }
            bucketArr[bucketIndex][indexArr[bucketIndex]] = arr[i];
            indexArr[bucketIndex]++;//元素个数从0开始累加
        }

        //用快速排序来给每个桶来排序，并且重新给arr来赋值
        for(int i=0;i<bucketArr.length;i++){
            //如果某个桶没有元素，跳过
            if(indexArr[i]==0){
                continue;
            }
            quickSorts(bucketArr[i],0,indexArr[i]-1);
            for(int j=0,k=0;j<indexArr[i];j++){
                arr[k] = bucketArr[i][j];
                k++;
            }
        }
    }

    private void quickSorts(int[] arr, int p, int r) {
        //递归终止条件
        if(p>=r){
            return;
        }

        int q = partition(arr,p,r);
        quickSorts(arr,p,q-1);
        quickSorts(arr,q+1,r);

    }

    private int partition(int[] arr, int p, int r) {
        int proite = arr[r];
        int i = p;
        for(int j=p;j<r;j++){
            if(arr[j]<proite){
                swap(arr,i,j);
                i++;
            }
        }
        swap(arr,i,r);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        if(i==j){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 数组扩容
     * @param bucketArr
     * @param bucketIndex
     */
    private void bucketAddSizeToDouble(int[][] bucketArr, int bucketIndex) {
        int[] oldArr = bucketArr[bucketIndex];
        int[] newArr = new int[oldArr.length*2];
        for(int i=0;i<oldArr.length;i++){
            newArr[i] = oldArr[i];
        }
        bucketArr[bucketIndex] = newArr;
    }

}
